/**
 * 二维数组，每次可以向右或者向下走。
 * 也可以花一步走到与当前元素值不互质的位置。
 * 问从左上到右下最少步数
 * 建图。每个位置有两条边出去，权值均为1。
 * 然后考虑特殊走法。
 * 令Fi包含所有元素值是i倍数的位置, i是质数
 * 令Fi的所有位置到i有一条边，权值为1；i到Fi的所有位置有一条边权值为0。
 * 然后跑一个最短路.
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

using llt = long long;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vll = vector<llt>;

template<typename T>
void input(vector<T>&v, int n){
    v.assign(n + 1, {});
    for(int i=1;i<=n;++i) cin >> v[i];
}

template<typename T>
istream & operator >> (istream & is, vector<T> & v){
    for(auto & i : v) is >> i;
    return is;
}

struct ShortestPath_Dijkstra{

using weight_t = long long;

struct edge_t{
    int from;
    int to;
    weight_t w;
    edge_t(int a, int b, weight_t c):from(a),to(b),w(c){}
};

vector<vector<int>> g;
vector<edge_t> edges;

ShortestPath_Dijkstra():q([](const pair<int, weight_t> & a, const pair<int, weight_t> & b){
    if(a.second != b.second) return a.second > b.second;
    return a.first > b.first;
}){}

void init(int n, int m){
    g.assign(n + 1, {});
    edges.clear();
    edges.reserve(m);
}

void mkDiEdge(int a, int b, int c){
    g[a].emplace_back(edges.size());
    edges.push_back({a, b, c});    
}

void mkBiEdge(int a, int b, int c){
    mkDiEdge(a, b, c);
    mkDiEdge(b, a, c);
}

void Dijkstra(int s){
    int n = g.size() - 1;
    q.clear();
    d.assign(n + 1, inf());
    pre.assign(n + 1, 0);
    flag.assign(n + 1, 0);
    q.push({s, d[s] = 0});
    while(1){
        while(not q.empty() and flag[q.top().first]) q.pop();
        if(q.empty()) break;

        auto h = q.top(); q.pop();
        flag[h.first] = 1;

        int v;
        weight_t tmp;
        for(int i : g[h.first]){
            const auto & e = edges[i];
            if(flag[v = e.to] or d[v] <= (tmp = h.second + e.w)) continue;
            q.push({v, d[v] = tmp});
            pre[v] = h.first;
        }
    }
    return;
}

static weight_t inf() {
    static const weight_t INF = 0x7F8F9FAFBFCFDFEF;
    return INF;
}

__gnu_pbds::priority_queue<
    pair<int, weight_t>, 
    function<bool(const pair<int, weight_t> &, const pair<int, weight_t> &)>
> q;

vector<weight_t> d; // d[i]表示s到i的最短距离
vector<int> pre; // 从s到i的最短路径会经过pre[i]
vector<int> flag; // 标记数组

}Dij;

llt const INF = 0x1F2F3F4F5F6F7F8F;
llt const NINF = -INF;
llt const MOD = 998244353LL;

int N, M;
vector<vi> Board;
vector<vi> F;

inline int f(int r, int c){
    return r * M + c + 1;
}

void work(){
    cin >> N >> M;
    Board.assign(N, vi(M, 0));
    cin >> Board;
    
    F.assign(100001, {});
    for(int i=0;i<N;++i)for(int j=0;j<M;++j){
        auto pos = f(i, j);
        auto a = Board[i][j];
        for(llt k=2;k*k<=a;++k){
            if(0 == a % k){
                F[k].emplace_back(pos);
                while(0 == a % k) a /= k;
            }
        }
        if(1 != a) F[a].emplace_back(pos);
    }

    int vn = N * M + 100001;
    Dij.init(vn, vn * 2);
    for(int i=0;i<N;++i)for(int j=0;j<M;++j){
        int a = f(i, j);
        if(i + 1 < N){
            int b = f(i + 1, j);
            Dij.mkDiEdge(a, b, 1);
        }
        if(j + 1 < M){
            int b = f(i, j + 1);
            Dij.mkDiEdge(a, b, 1);
        }
    }
    for(int i=0;i<100001;++i){
        if(F[i].empty()) continue;

        int a = N * M + i;
        for(auto b : F[i]){
            Dij.mkDiEdge(b, a, 1);
            Dij.mkDiEdge(a, b, 0);
        }
    }

    Dij.Dijkstra(1);
    cout << Dij.d[N * M] << endl;
    return;
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase; 
    while(nofkase--) work();    
    return 0;
}
